using System.Collections.Generic;
using System;
using Wintellect.PowerCollections;

namespace Algorithms
{
	public class Kruskal<T>
	{
		public List<T> Nodes = new List<T>();
		public OrderedMultiDictionary<float, Edge<T>> Edges = new OrderedMultiDictionary<float, Edge<T>>(true);

		public void AddNode(T newNode)
		{
			Nodes.Add(newNode);
		}

		public void AddEdge(T startNode, T endNode, float weight)
		{
			Edges.Add(weight, new Edge<T>(startNode, endNode, weight));
		}

		public List<Edge<T>> ComputeMinimalSpanningTree()
		{
			UnionFind<T> a = new UnionFind<T>();

			foreach (T node in Nodes)
			{
				a.MakeSet(node);
			}

			List<Edge<T>> result = new List<Edge<T>>(Nodes.Count - 1);

			foreach (Edge<T> edge in Edges.Values)
			{
				if (result.Count == Nodes.Count - 1)
				{

				}
				if (a.Find(edge.Start) != a.Find(edge.End))
				{
					result.Add(edge);
					a.Union(edge.Start, edge.End);
				}
			}

			return result;
		}

		public int CompareEdges(Edge<T> e1, Edge<T> e2)
		{
			return Math.Sign(e1.Weight - e2.Weight);
		}
	}

	public class Edge<T> : IComparable<Edge<T>>
	{
		public Edge(T start, T end, float weight)
		{
			Start = start;
			End = end;
			Weight = weight;
		}

		public T Start;
		public T End;
		public float Weight;

		public int CompareTo(Edge<T> other)
		{
			return Math.Sign(this.Weight - other.Weight);
		}
	}
}

